package String;

import java.util.Arrays;

public class KMP {

    /**
     * 构建前缀表
     * */
     static void getNext(int[] next, String s){
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.length(); i++) {
            while(j>=0 && s.charAt(i) != s.charAt(j+1)){
                j = next[j];
            }
            if(s.charAt(i) == s.charAt(j+1)){
                j++;
            }
            next[i] = j;
        }
    }

    public static int strStr(String haystack, String needle) {
         int n = needle.length();
         if (n==0){
             return 0;
         }
         int[] next = new int[n];
         getNext(next,needle);
         int j = -1;

         for (int i = 0; i < haystack.length(); i++) {

             while(j>=0 && haystack.charAt(i) != needle.charAt(j+1)){
                 j = next[j];
             }
             if(haystack.charAt(i) == needle.charAt(j+1)){
                j++;
             }
             //当j为模式串长度-1时，说明已经匹配完，当前i为文本串匹配位置的末尾
             //末尾下标减去模式串长度+1即匹配的开始位置
             if(j == n-1){
                return i-n+1;
             }
         }
         return -1;
    }

    public static void main(String[] args) {
        String needle = "ll";
        String hayjack = "hello";
        System.out.println(strStr(hayjack, needle));
    }
}
